Размещение баннеров

Представим, что международное круизное агентство Carnival Cruise Line решило себя разрекламировать с помощью баннеров и обратилось для этого к вам. Чтобы протестировать, велика ли от таких баннеров польза, их будет размещено всего 20 штук по всему миру. Вам надо выбрать 20 таких локаций для размещения, чтобы польза была большой и агентство продолжило с вами сотрудничать.

Агентство крупное, и у него есть несколько офисов по всему миру. Вблизи этих офисов оно и хочет разместить баннеры — легче договариваться и проверять результат. Также эти места должны быть популярны среди туристов.



In [1]:

    
import numpy as np
import pandas as pd
from sklearn.cluster import MeanShift

Для поиска оптимальных мест воспользуемся базой данных крупнейшей социальной сети, основанной на локациях — Foursquare.

Часть открытых данных есть, например, на сайте archive.org:

https://archive.org/details/201309_foursquare_dataset_umn

Скачаем любым удобным образом архив fsq.zip с этой страницы.

Нас будет интересовать файл checkins.dat.

Для удобной работы с этим документом преобразуем его к формату csv, удалив строки, не содержащие координат — они неинформативны для нас:



In [2]:

    
#Reading the data file
checkins = pd.read_csv('checkins.dat', sep='|', skipinitialspace=True, skiprows=[1], low_memory=False)
print(checkins.info())
checkins.head()









    



<class 'pandas.core.frame.DataFrame'>
RangeIndex: 1021967 entries, 0 to 1021966
Data columns (total 6 columns):
id                  1021967 non-null object
user_id             1021966 non-null float64
venue_id            1021966 non-null float64
latitude            396634 non-null float64
longitude           396634 non-null float64
created_at          1021966 non-null object
dtypes: float64(4), object(2)
memory usage: 46.8+ MB
None






    Out[2]:







  
    
      
      id
      user_id
      venue_id
      latitude
      longitude
      created_at
    
  
  
    
      0
      984301
      2041916.0
      5222.0
      NaN
      NaN
      2012-04-21 17:39:01
    
    
      1
      984222
      15824.0
      5222.0
      38.895112
      -77.036366
      2012-04-21 17:43:47
    
    
      2
      984315
      1764391.0
      5222.0
      NaN
      NaN
      2012-04-21 17:37:18
    
    
      3
      984234
      44652.0
      5222.0
      33.800745
      -84.410520
      2012-04-21 17:43:43
    
    
      4
      984249
      2146840.0
      5222.0
      NaN
      NaN
      2012-04-21 17:42:58



In [3]:

    
#Stripping columns names (deleting whitespaces)
checkins.columns = checkins.columns.str.strip()

#Dropping rows with NaN values
checkins = checkins.dropna()
print('Shape without NaN: %s' % str(checkins.shape))
checkins.head()









    



Shape without NaN: (396634, 6)






    Out[3]:







  
    
      
      id
      user_id
      venue_id
      latitude
      longitude
      created_at
    
  
  
    
      1
      984222
      15824.0
      5222.0
      38.895112
      -77.036366
      2012-04-21 17:43:47
    
    
      3
      984234
      44652.0
      5222.0
      33.800745
      -84.410520
      2012-04-21 17:43:43
    
    
      7
      984291
      105054.0
      5222.0
      45.523452
      -122.676207
      2012-04-21 17:39:22
    
    
      9
      984318
      2146539.0
      5222.0
      40.764462
      -111.904565
      2012-04-21 17:35:46
    
    
      10
      984232
      93870.0
      380645.0
      33.448377
      -112.074037
      2012-04-21 17:38:18

Теперь необходимо кластеризовать данные координаты, чтобы выявить центры скоплений туристов. Поскольку баннеры имеют сравнительно небольшую площадь действия, нам нужен алгоритм, позволяющий ограничить размер кластера и не зависящий от количества кластеров.

Эта задача — хороший повод познакомиться с алгоритмом MeanShift, который мы обошли стороной в основной части лекций. Его описание при желании можно посмотреть в sklearn user guide, а чуть позже появится дополнительное видео с обзором этого и некоторых других алгоритмов кластеризации. Используйте MeanShift, указав bandwidth=0.1, что в переводе из градусов в метры колеблется примерно от 5 до 10 км в средних широтах.

Примечание: на 396634 строках кластеризация будет работать долго. Быть очень терпеливым не возбраняется — результат от этого только улучшится. Но для того, чтобы сдать задание, понадобится сабсет из первых 100 тысяч строк. Это компромисс между качеством и затраченным временем. Обучение алгоритма на всём датасете занимает около часа, а на 100 тыс. строк — примерно 2 минуты, однако этого достаточно для получения корректных результатов.



In [4]:

    
#Array for clustering (100000 entries and 'latitude' and 'longitude' columns)
checkins_cl = checkins.iloc[:100000, :].loc[:, ['latitude', 'longitude']]
print('Shape: ' + str(checkins_cl.shape))
checkins_cl.head()









    



Shape: (100000, 2)






    Out[4]:







  
    
      
      latitude
      longitude
    
  
  
    
      1
      38.895112
      -77.036366
    
    
      3
      33.800745
      -84.410520
    
    
      7
      45.523452
      -122.676207
    
    
      9
      40.764462
      -111.904565
    
    
      10
      33.448377
      -112.074037



In [5]:

    
#Clustering with MeanShift
ms = MeanShift(bandwidth=0.1)
ms.fit(checkins_cl)









    Out[5]:





MeanShift(bandwidth=0.1, bin_seeding=False, cluster_all=True, min_bin_freq=1,
     n_jobs=1, seeds=None)

Некоторые из получившихся кластеров содержат слишком мало точек — такие кластеры не интересны рекламодателям. Поэтому надо определить, какие из кластеров содержат, скажем, больше 15 элементов. Центры этих кластеров и являются оптимальными для размещения.



In [6]:

    
#Labels and cluster centers
labels = ms.labels_
cluster_centers = ms.cluster_centers_

print('Number of estimated clusters : %d' % len(cluster_centers))

#Count the number of items for each cluster
labels_unique, labels_counts = np.unique(labels, return_counts=True)
for lbl, cnt in zip(labels_unique, labels_counts):
    print(lbl, cnt)









    



Number of estimated clusters : 3230
(0, 12506)
(1, 4692)
(2, 3994)
(3, 3363)
(4, 3526)
(5, 2409)
(6, 2297)
(7, 1601)
(8, 1526)
(9, 1378)
(10, 1298)
(11, 1081)
(12, 1006)
(13, 1007)
(14, 714)
(15, 868)
(16, 870)
(17, 645)
(18, 808)
(19, 807)
(20, 612)
(21, 722)
(22, 754)
(23, 747)
(24, 539)
(25, 656)
(26, 580)
(27, 577)
(28, 679)
(29, 564)
(30, 594)
(31, 907)
(32, 449)
(33, 502)
(34, 452)
(35, 104)
(36, 431)
(37, 410)
(38, 388)
(39, 400)
(40, 369)
(41, 367)
(42, 384)
(43, 347)
(44, 345)
(45, 342)
(46, 314)
(47, 273)
(48, 314)
(49, 316)
(50, 355)
(51, 281)
(52, 336)
(53, 293)
(54, 271)
(55, 246)
(56, 263)
(57, 258)
(58, 254)
(59, 243)
(60, 229)
(61, 291)
(62, 182)
(63, 155)
(64, 137)
(65, 193)
(66, 186)
(67, 197)
(68, 196)
(69, 189)
(70, 191)
(71, 187)
(72, 203)
(73, 178)
(74, 192)
(75, 169)
(76, 173)
(77, 153)
(78, 157)
(79, 199)
(80, 220)
(81, 164)
(82, 162)
(83, 155)
(84, 126)
(85, 152)
(86, 56)
(87, 100)
(88, 141)
(89, 142)
(90, 190)
(91, 117)
(92, 138)
(93, 133)
(94, 135)
(95, 131)
(96, 134)
(97, 122)
(98, 130)
(99, 109)
(100, 132)
(101, 135)
(102, 135)
(103, 120)
(104, 119)
(105, 116)
(106, 110)
(107, 91)
(108, 114)
(109, 114)
(110, 79)
(111, 98)
(112, 112)
(113, 74)
(114, 110)
(115, 67)
(116, 126)
(117, 106)
(118, 110)
(119, 74)
(120, 103)
(121, 102)
(122, 101)
(123, 100)
(124, 85)
(125, 99)
(126, 72)
(127, 99)
(128, 118)
(129, 95)
(130, 98)
(131, 84)
(132, 27)
(133, 99)
(134, 95)
(135, 97)
(136, 97)
(137, 92)
(138, 91)
(139, 103)
(140, 71)
(141, 95)
(142, 87)
(143, 99)
(144, 95)
(145, 33)
(146, 85)
(147, 65)
(148, 121)
(149, 78)
(150, 83)
(151, 81)
(152, 79)
(153, 101)
(154, 79)
(155, 61)
(156, 79)
(157, 78)
(158, 42)
(159, 84)
(160, 78)
(161, 68)
(162, 57)
(163, 63)
(164, 76)
(165, 74)
(166, 80)
(167, 76)
(168, 52)
(169, 56)
(170, 74)
(171, 74)
(172, 74)
(173, 73)
(174, 51)
(175, 71)
(176, 76)
(177, 77)
(178, 69)
(179, 78)
(180, 69)
(181, 69)
(182, 44)
(183, 68)
(184, 68)
(185, 52)
(186, 67)
(187, 67)
(188, 66)
(189, 66)
(190, 65)
(191, 53)
(192, 59)
(193, 64)
(194, 36)
(195, 63)
(196, 63)
(197, 54)
(198, 63)
(199, 62)
(200, 84)
(201, 43)
(202, 61)
(203, 61)
(204, 61)
(205, 61)
(206, 60)
(207, 58)
(208, 50)
(209, 56)
(210, 24)
(211, 46)
(212, 58)
(213, 58)
(214, 57)
(215, 58)
(216, 57)
(217, 56)
(218, 56)
(219, 48)
(220, 56)
(221, 56)
(222, 57)
(223, 42)
(224, 55)
(225, 38)
(226, 37)
(227, 82)
(228, 51)
(229, 37)
(230, 53)
(231, 54)
(232, 53)
(233, 134)
(234, 52)
(235, 52)
(236, 58)
(237, 50)
(238, 50)
(239, 38)
(240, 42)
(241, 44)
(242, 51)
(243, 52)
(244, 50)
(245, 50)
(246, 50)
(247, 50)
(248, 50)
(249, 36)
(250, 49)
(251, 49)
(252, 52)
(253, 48)
(254, 49)
(255, 44)
(256, 46)
(257, 50)
(258, 58)
(259, 47)
(260, 38)
(261, 44)
(262, 47)
(263, 49)
(264, 46)
(265, 46)
(266, 38)
(267, 49)
(268, 46)
(269, 40)
(270, 44)
(271, 45)
(272, 49)
(273, 43)
(274, 45)
(275, 45)
(276, 45)
(277, 45)
(278, 45)
(279, 44)
(280, 43)
(281, 40)
(282, 32)
(283, 16)
(284, 45)
(285, 37)
(286, 43)
(287, 36)
(288, 42)
(289, 42)
(290, 45)
(291, 42)
(292, 44)
(293, 47)
(294, 42)
(295, 51)
(296, 41)
(297, 41)
(298, 41)
(299, 40)
(300, 40)
(301, 40)
(302, 33)
(303, 40)
(304, 59)
(305, 53)
(306, 41)
(307, 39)
(308, 37)
(309, 30)
(310, 39)
(311, 35)
(312, 24)
(313, 38)
(314, 38)
(315, 38)
(316, 32)
(317, 38)
(318, 38)
(319, 59)
(320, 42)
(321, 35)
(322, 41)
(323, 37)
(324, 35)
(325, 37)
(326, 36)
(327, 36)
(328, 43)
(329, 36)
(330, 38)
(331, 36)
(332, 37)
(333, 33)
(334, 11)
(335, 24)
(336, 35)
(337, 35)
(338, 35)
(339, 34)
(340, 34)
(341, 44)
(342, 27)
(343, 33)
(344, 34)
(345, 34)
(346, 34)
(347, 34)
(348, 35)
(349, 37)
(350, 35)
(351, 33)
(352, 33)
(353, 37)
(354, 33)
(355, 33)
(356, 27)
(357, 31)
(358, 33)
(359, 42)
(360, 21)
(361, 32)
(362, 32)
(363, 32)
(364, 37)
(365, 46)
(366, 32)
(367, 37)
(368, 32)
(369, 32)
(370, 31)
(371, 31)
(372, 31)
(373, 31)
(374, 31)
(375, 28)
(376, 31)
(377, 28)
(378, 25)
(379, 37)
(380, 31)
(381, 31)
(382, 31)
(383, 17)
(384, 25)
(385, 30)
(386, 34)
(387, 30)
(388, 28)
(389, 32)
(390, 12)
(391, 32)
(392, 15)
(393, 27)
(394, 64)
(395, 29)
(396, 32)
(397, 29)
(398, 29)
(399, 29)
(400, 16)
(401, 29)
(402, 29)
(403, 29)
(404, 28)
(405, 28)
(406, 28)
(407, 28)
(408, 25)
(409, 24)
(410, 28)
(411, 28)
(412, 28)
(413, 28)
(414, 29)
(415, 28)
(416, 28)
(417, 28)
(418, 28)
(419, 26)
(420, 28)
(421, 27)
(422, 27)
(423, 27)
(424, 26)
(425, 27)
(426, 27)
(427, 27)
(428, 27)
(429, 27)
(430, 28)
(431, 27)
(432, 27)
(433, 27)
(434, 26)
(435, 23)
(436, 27)
(437, 26)
(438, 26)
(439, 27)
(440, 26)
(441, 28)
(442, 25)
(443, 26)
(444, 26)
(445, 29)
(446, 24)
(447, 26)
(448, 26)
(449, 25)
(450, 16)
(451, 26)
(452, 25)
(453, 19)
(454, 23)
(455, 24)
(456, 24)
(457, 25)
(458, 24)
(459, 24)
(460, 24)
(461, 24)
(462, 20)
(463, 24)
(464, 26)
(465, 21)
(466, 32)
(467, 22)
(468, 24)
(469, 23)
(470, 23)
(471, 21)
(472, 14)
(473, 23)
(474, 23)
(475, 23)
(476, 23)
(477, 23)
(478, 23)
(479, 24)
(480, 20)
(481, 23)
(482, 23)
(483, 23)
(484, 22)
(485, 22)
(486, 23)
(487, 21)
(488, 22)
(489, 22)
(490, 24)
(491, 22)
(492, 29)
(493, 22)
(494, 22)
(495, 22)
(496, 22)
(497, 22)
(498, 22)
(499, 22)
(500, 21)
(501, 21)
(502, 17)
(503, 21)
(504, 21)
(505, 21)
(506, 21)
(507, 21)
(508, 21)
(509, 21)
(510, 31)
(511, 17)
(512, 20)
(513, 20)
(514, 20)
(515, 15)
(516, 20)
(517, 20)
(518, 20)
(519, 19)
(520, 20)
(521, 20)
(522, 19)
(523, 23)
(524, 19)
(525, 21)
(526, 19)
(527, 18)
(528, 18)
(529, 19)
(530, 19)
(531, 19)
(532, 19)
(533, 19)
(534, 19)
(535, 21)
(536, 19)
(537, 19)
(538, 19)
(539, 18)
(540, 15)
(541, 27)
(542, 18)
(543, 21)
(544, 18)
(545, 18)
(546, 18)
(547, 18)
(548, 18)
(549, 18)
(550, 18)
(551, 18)
(552, 18)
(553, 18)
(554, 18)
(555, 18)
(556, 18)
(557, 17)
(558, 17)
(559, 17)
(560, 17)
(561, 17)
(562, 13)
(563, 14)
(564, 17)
(565, 17)
(566, 17)
(567, 17)
(568, 17)
(569, 17)
(570, 17)
(571, 17)
(572, 13)
(573, 16)
(574, 16)
(575, 16)
(576, 16)
(577, 16)
(578, 16)
(579, 16)
(580, 16)
(581, 16)
(582, 26)
(583, 19)
(584, 16)
(585, 11)
(586, 16)
(587, 15)
(588, 16)
(589, 16)
(590, 16)
(591, 15)
(592, 19)
(593, 16)
(594, 22)
(595, 16)
(596, 15)
(597, 15)
(598, 15)
(599, 15)
(600, 15)
(601, 15)
(602, 15)
(603, 15)
(604, 15)
(605, 15)
(606, 15)
(607, 12)
(608, 17)
(609, 15)
(610, 15)
(611, 15)
(612, 15)
(613, 14)
(614, 15)
(615, 15)
(616, 15)
(617, 15)
(618, 15)
(619, 15)
(620, 11)
(621, 14)
(622, 15)
(623, 14)
(624, 14)
(625, 14)
(626, 14)
(627, 14)
(628, 13)
(629, 14)
(630, 15)
(631, 14)
(632, 14)
(633, 14)
(634, 15)
(635, 14)
(636, 14)
(637, 15)
(638, 14)
(639, 14)
(640, 18)
(641, 14)
(642, 14)
(643, 13)
(644, 11)
(645, 13)
(646, 13)
(647, 13)
(648, 13)
(649, 13)
(650, 13)
(651, 13)
(652, 11)
(653, 13)
(654, 13)
(655, 13)
(656, 10)
(657, 13)
(658, 13)
(659, 13)
(660, 12)
(661, 13)
(662, 13)
(663, 16)
(664, 13)
(665, 13)
(666, 13)
(667, 13)
(668, 13)
(669, 13)
(670, 13)
(671, 13)
(672, 16)
(673, 13)
(674, 13)
(675, 10)
(676, 12)
(677, 12)
(678, 12)
(679, 12)
(680, 12)
(681, 12)
(682, 12)
(683, 12)
(684, 13)
(685, 12)
(686, 12)
(687, 12)
(688, 12)
(689, 12)
(690, 12)
(691, 12)
(692, 11)
(693, 12)
(694, 12)
(695, 12)
(696, 12)
(697, 7)
(698, 12)
(699, 12)
(700, 13)
(701, 8)
(702, 12)
(703, 19)
(704, 12)
(705, 11)
(706, 8)
(707, 12)
(708, 11)
(709, 12)
(710, 11)
(711, 10)
(712, 11)
(713, 11)
(714, 13)
(715, 11)
(716, 11)
(717, 11)
(718, 11)
(719, 11)
(720, 11)
(721, 10)
(722, 11)
(723, 26)
(724, 11)
(725, 11)
(726, 11)
(727, 11)
(728, 9)
(729, 11)
(730, 11)
(731, 11)
(732, 11)
(733, 11)
(734, 11)
(735, 11)
(736, 11)
(737, 11)
(738, 10)
(739, 11)
(740, 11)
(741, 9)
(742, 11)
(743, 11)
(744, 11)
(745, 11)
(746, 11)
(747, 11)
(748, 12)
(749, 11)
(750, 15)
(751, 11)
(752, 12)
(753, 10)
(754, 10)
(755, 10)
(756, 10)
(757, 11)
(758, 10)
(759, 10)
(760, 10)
(761, 10)
(762, 10)
(763, 10)
(764, 10)
(765, 10)
(766, 10)
(767, 10)
(768, 10)
(769, 10)
(770, 10)
(771, 10)
(772, 10)
(773, 10)
(774, 10)
(775, 10)
(776, 10)
(777, 10)
(778, 10)
(779, 10)
(780, 10)
(781, 9)
(782, 11)
(783, 10)
(784, 10)
(785, 10)
(786, 10)
(787, 10)
(788, 10)
(789, 10)
(790, 10)
(791, 10)
(792, 10)
(793, 10)
(794, 10)
(795, 10)
(796, 10)
(797, 10)
(798, 10)
(799, 11)
(800, 10)
(801, 9)
(802, 9)
(803, 9)
(804, 9)
(805, 9)
(806, 9)
(807, 11)
(808, 8)
(809, 9)
(810, 9)
(811, 9)
(812, 9)
(813, 9)
(814, 9)
(815, 9)
(816, 8)
(817, 9)
(818, 9)
(819, 9)
(820, 9)
(821, 9)
(822, 9)
(823, 9)
(824, 9)
(825, 9)
(826, 9)
(827, 9)
(828, 9)
(829, 8)
(830, 9)
(831, 9)
(832, 9)
(833, 9)
(834, 9)
(835, 9)
(836, 9)
(837, 9)
(838, 9)
(839, 9)
(840, 9)
(841, 9)
(842, 9)
(843, 8)
(844, 9)
(845, 9)
(846, 8)
(847, 9)
(848, 9)
(849, 9)
(850, 10)
(851, 9)
(852, 9)
(853, 9)
(854, 10)
(855, 9)
(856, 9)
(857, 9)
(858, 9)
(859, 8)
(860, 9)
(861, 9)
(862, 5)
(863, 9)
(864, 9)
(865, 9)
(866, 9)
(867, 9)
(868, 8)
(869, 8)
(870, 8)
(871, 8)
(872, 8)
(873, 4)
(874, 8)
(875, 8)
(876, 8)
(877, 5)
(878, 8)
(879, 8)
(880, 8)
(881, 8)
(882, 8)
(883, 8)
(884, 8)
(885, 8)
(886, 8)
(887, 8)
(888, 8)
(889, 8)
(890, 8)
(891, 8)
(892, 8)
(893, 8)
(894, 8)
(895, 8)
(896, 8)
(897, 8)
(898, 23)
(899, 8)
(900, 8)
(901, 8)
(902, 8)
(903, 8)
(904, 8)
(905, 8)
(906, 8)
(907, 8)
(908, 8)
(909, 8)
(910, 8)
(911, 6)
(912, 8)
(913, 11)
(914, 8)
(915, 8)
(916, 8)
(917, 7)
(918, 7)
(919, 7)
(920, 7)
(921, 7)
(922, 7)
(923, 7)
(924, 7)
(925, 7)
(926, 7)
(927, 7)
(928, 7)
(929, 7)
(930, 7)
(931, 7)
(932, 7)
(933, 7)
(934, 7)
(935, 7)
(936, 7)
(937, 7)
(938, 7)
(939, 7)
(940, 7)
(941, 6)
(942, 7)
(943, 7)
(944, 7)
(945, 7)
(946, 7)
(947, 7)
(948, 7)
(949, 7)
(950, 7)
(951, 7)
(952, 10)
(953, 7)
(954, 7)
(955, 7)
(956, 7)
(957, 8)
(958, 7)
(959, 7)
(960, 7)
(961, 7)
(962, 7)
(963, 7)
(964, 7)
(965, 7)
(966, 7)
(967, 7)
(968, 7)
(969, 7)
(970, 7)
(971, 7)
(972, 7)
(973, 7)
(974, 7)
(975, 7)
(976, 7)
(977, 7)
(978, 7)
(979, 7)
(980, 7)
(981, 7)
(982, 6)
(983, 7)
(984, 7)
(985, 7)
(986, 7)
(987, 7)
(988, 7)
(989, 7)
(990, 7)
(991, 7)
(992, 7)
(993, 7)
(994, 7)
(995, 7)
(996, 7)
(997, 7)
(998, 7)
(999, 7)
(1000, 6)
(1001, 6)
(1002, 6)
(1003, 6)
(1004, 6)
(1005, 6)
(1006, 6)
(1007, 6)
(1008, 6)
(1009, 6)
(1010, 6)
(1011, 6)
(1012, 6)
(1013, 6)
(1014, 6)
(1015, 6)
(1016, 6)
(1017, 6)
(1018, 7)
(1019, 6)
(1020, 6)
(1021, 6)
(1022, 6)
(1023, 6)
(1024, 6)
(1025, 6)
(1026, 6)
(1027, 6)
(1028, 6)
(1029, 6)
(1030, 6)
(1031, 6)
(1032, 6)
(1033, 6)
(1034, 5)
(1035, 6)
(1036, 6)
(1037, 7)
(1038, 6)
(1039, 6)
(1040, 6)
(1041, 6)
(1042, 6)
(1043, 6)
(1044, 6)
(1045, 6)
(1046, 6)
(1047, 6)
(1048, 6)
(1049, 6)
(1050, 6)
(1051, 6)
(1052, 6)
(1053, 6)
(1054, 6)
(1055, 6)
(1056, 6)
(1057, 6)
(1058, 6)
(1059, 6)
(1060, 6)
(1061, 6)
(1062, 6)
(1063, 6)
(1064, 6)
(1065, 6)
(1066, 6)
(1067, 6)
(1068, 7)
(1069, 6)
(1070, 6)
(1071, 6)
(1072, 6)
(1073, 6)
(1074, 6)
(1075, 6)
(1076, 6)
(1077, 6)
(1078, 6)
(1079, 6)
(1080, 6)
(1081, 6)
(1082, 6)
(1083, 6)
(1084, 6)
(1085, 6)
(1086, 6)
(1087, 6)
(1088, 6)
(1089, 6)
(1090, 6)
(1091, 6)
(1092, 6)
(1093, 6)
(1094, 6)
(1095, 6)
(1096, 6)
(1097, 6)
(1098, 6)
(1099, 6)
(1100, 6)
(1101, 6)
(1102, 6)
(1103, 6)
(1104, 6)
(1105, 6)
(1106, 5)
(1107, 5)
(1108, 5)
(1109, 5)
(1110, 5)
(1111, 5)
(1112, 4)
(1113, 6)
(1114, 5)
(1115, 5)
(1116, 5)
(1117, 5)
(1118, 5)
(1119, 5)
(1120, 5)
(1121, 5)
(1122, 5)
(1123, 5)
(1124, 5)
(1125, 5)
(1126, 5)
(1127, 5)
(1128, 5)
(1129, 5)
(1130, 5)
(1131, 5)
(1132, 5)
(1133, 5)
(1134, 5)
(1135, 5)
(1136, 5)
(1137, 5)
(1138, 5)
(1139, 5)
(1140, 5)
(1141, 5)
(1142, 5)
(1143, 5)
(1144, 5)
(1145, 5)
(1146, 5)
(1147, 5)
(1148, 5)
(1149, 5)
(1150, 5)
(1151, 5)
(1152, 5)
(1153, 5)
(1154, 5)
(1155, 5)
(1156, 5)
(1157, 5)
(1158, 5)
(1159, 5)
(1160, 5)
(1161, 5)
(1162, 5)
(1163, 5)
(1164, 5)
(1165, 5)
(1166, 5)
(1167, 5)
(1168, 5)
(1169, 5)
(1170, 5)
(1171, 5)
(1172, 5)
(1173, 4)
(1174, 5)
(1175, 5)
(1176, 5)
(1177, 5)
(1178, 5)
(1179, 5)
(1180, 5)
(1181, 5)
(1182, 5)
(1183, 5)
(1184, 5)
(1185, 5)
(1186, 5)
(1187, 5)
(1188, 5)
(1189, 5)
(1190, 5)
(1191, 5)
(1192, 5)
(1193, 5)
(1194, 5)
(1195, 5)
(1196, 5)
(1197, 5)
(1198, 5)
(1199, 5)
(1200, 5)
(1201, 5)
(1202, 5)
(1203, 5)
(1204, 5)
(1205, 5)
(1206, 9)
(1207, 5)
(1208, 5)
(1209, 5)
(1210, 5)
(1211, 5)
(1212, 5)
(1213, 5)
(1214, 5)
(1215, 5)
(1216, 5)
(1217, 5)
(1218, 5)
(1219, 5)
(1220, 5)
(1221, 5)
(1222, 5)
(1223, 7)
(1224, 3)
(1225, 5)
(1226, 5)
(1227, 5)
(1228, 5)
(1229, 5)
(1230, 5)
(1231, 5)
(1232, 5)
(1233, 5)
(1234, 5)
(1235, 4)
(1236, 4)
(1237, 4)
(1238, 4)
(1239, 4)
(1240, 4)
(1241, 4)
(1242, 4)
(1243, 4)
(1244, 4)
(1245, 4)
(1246, 4)
(1247, 4)
(1248, 4)
(1249, 4)
(1250, 4)
(1251, 4)
(1252, 4)
(1253, 4)
(1254, 4)
(1255, 4)
(1256, 4)
(1257, 4)
(1258, 4)
(1259, 4)
(1260, 4)
(1261, 4)
(1262, 4)
(1263, 4)
(1264, 4)
(1265, 4)
(1266, 4)
(1267, 4)
(1268, 19)
(1269, 4)
(1270, 4)
(1271, 4)
(1272, 4)
(1273, 4)
(1274, 4)
(1275, 4)
(1276, 4)
(1277, 4)
(1278, 21)
(1279, 4)
(1280, 4)
(1281, 4)
(1282, 4)
(1283, 4)
(1284, 4)
(1285, 4)
(1286, 4)
(1287, 4)
(1288, 4)
(1289, 4)
(1290, 4)
(1291, 4)
(1292, 4)
(1293, 4)
(1294, 4)
(1295, 4)
(1296, 4)
(1297, 4)
(1298, 4)
(1299, 10)
(1300, 4)
(1301, 4)
(1302, 4)
(1303, 4)
(1304, 4)
(1305, 4)
(1306, 4)
(1307, 4)
(1308, 4)
(1309, 4)
(1310, 5)
(1311, 4)
(1312, 4)
(1313, 4)
(1314, 4)
(1315, 4)
(1316, 4)
(1317, 4)
(1318, 4)
(1319, 6)
(1320, 4)
(1321, 4)
(1322, 4)
(1323, 4)
(1324, 4)
(1325, 4)
(1326, 4)
(1327, 4)
(1328, 4)
(1329, 4)
(1330, 4)
(1331, 4)
(1332, 4)
(1333, 4)
(1334, 4)
(1335, 4)
(1336, 4)
(1337, 4)
(1338, 4)
(1339, 4)
(1340, 4)
(1341, 4)
(1342, 4)
(1343, 4)
(1344, 4)
(1345, 4)
(1346, 4)
(1347, 4)
(1348, 4)
(1349, 4)
(1350, 4)
(1351, 4)
(1352, 4)
(1353, 9)
(1354, 4)
(1355, 4)
(1356, 4)
(1357, 4)
(1358, 4)
(1359, 4)
(1360, 4)
(1361, 4)
(1362, 4)
(1363, 5)
(1364, 4)
(1365, 4)
(1366, 4)
(1367, 4)
(1368, 4)
(1369, 4)
(1370, 4)
(1371, 4)
(1372, 4)
(1373, 4)
(1374, 4)
(1375, 4)
(1376, 4)
(1377, 4)
(1378, 4)
(1379, 4)
(1380, 4)
(1381, 4)
(1382, 4)
(1383, 4)
(1384, 4)
(1385, 4)
(1386, 4)
(1387, 4)
(1388, 4)
(1389, 4)
(1390, 4)
(1391, 4)
(1392, 4)
(1393, 4)
(1394, 4)
(1395, 4)
(1396, 4)
(1397, 4)
(1398, 4)
(1399, 4)
(1400, 4)
(1401, 4)
(1402, 4)
(1403, 4)
(1404, 4)
(1405, 4)
(1406, 4)
(1407, 4)
(1408, 4)
(1409, 4)
(1410, 4)
(1411, 4)
(1412, 4)
(1413, 4)
(1414, 4)
(1415, 4)
(1416, 4)
(1417, 5)
(1418, 4)
(1419, 4)
(1420, 4)
(1421, 4)
(1422, 4)
(1423, 4)
(1424, 4)
(1425, 4)
(1426, 4)
(1427, 4)
(1428, 4)
(1429, 7)
(1430, 4)
(1431, 4)
(1432, 4)
(1433, 4)
(1434, 3)
(1435, 3)
(1436, 3)
(1437, 3)
(1438, 3)
(1439, 3)
(1440, 3)
(1441, 3)
(1442, 3)
(1443, 3)
(1444, 3)
(1445, 3)
(1446, 3)
(1447, 3)
(1448, 3)
(1449, 3)
(1450, 3)
(1451, 3)
(1452, 3)
(1453, 3)
(1454, 3)
(1455, 3)
(1456, 3)
(1457, 3)
(1458, 3)
(1459, 3)
(1460, 3)
(1461, 3)
(1462, 3)
(1463, 3)
(1464, 3)
(1465, 3)
(1466, 3)
(1467, 3)
(1468, 3)
(1469, 3)
(1470, 3)
(1471, 3)
(1472, 3)
(1473, 3)
(1474, 3)
(1475, 3)
(1476, 3)
(1477, 3)
(1478, 3)
(1479, 3)
(1480, 12)
(1481, 3)
(1482, 3)
(1483, 3)
(1484, 3)
(1485, 3)
(1486, 2)
(1487, 3)
(1488, 3)
(1489, 3)
(1490, 3)
(1491, 3)
(1492, 3)
(1493, 3)
(1494, 3)
(1495, 3)
(1496, 3)
(1497, 3)
(1498, 3)
(1499, 3)
(1500, 3)
(1501, 3)
(1502, 3)
(1503, 3)
(1504, 6)
(1505, 3)
(1506, 3)
(1507, 3)
(1508, 3)
(1509, 3)
(1510, 3)
(1511, 3)
(1512, 3)
(1513, 3)
(1514, 3)
(1515, 3)
(1516, 4)
(1517, 3)
(1518, 3)
(1519, 3)
(1520, 3)
(1521, 3)
(1522, 3)
(1523, 3)
(1524, 3)
(1525, 3)
(1526, 3)
(1527, 3)
(1528, 3)
(1529, 3)
(1530, 3)
(1531, 3)
(1532, 3)
(1533, 3)
(1534, 3)
(1535, 3)
(1536, 3)
(1537, 3)
(1538, 3)
(1539, 3)
(1540, 3)
(1541, 3)
(1542, 3)
(1543, 3)
(1544, 3)
(1545, 3)
(1546, 3)
(1547, 3)
(1548, 3)
(1549, 3)
(1550, 3)
(1551, 3)
(1552, 3)
(1553, 3)
(1554, 3)
(1555, 3)
(1556, 3)
(1557, 3)
(1558, 3)
(1559, 3)
(1560, 3)
(1561, 3)
(1562, 3)
(1563, 3)
(1564, 3)
(1565, 3)
(1566, 3)
(1567, 3)
(1568, 3)
(1569, 3)
(1570, 3)
(1571, 3)
(1572, 3)
(1573, 3)
(1574, 3)
(1575, 3)
(1576, 3)
(1577, 3)
(1578, 3)
(1579, 3)
(1580, 3)
(1581, 3)
(1582, 3)
(1583, 3)
(1584, 3)
(1585, 3)
(1586, 3)
(1587, 3)
(1588, 6)
(1589, 3)
(1590, 3)
(1591, 3)
(1592, 3)
(1593, 3)
(1594, 3)
(1595, 3)
(1596, 3)
(1597, 3)
(1598, 3)
(1599, 3)
(1600, 3)
(1601, 3)
(1602, 3)
(1603, 3)
(1604, 3)
(1605, 3)
(1606, 3)
(1607, 3)
(1608, 3)
(1609, 3)
(1610, 3)
(1611, 3)
(1612, 3)
(1613, 3)
(1614, 3)
(1615, 4)
(1616, 3)
(1617, 3)
(1618, 3)
(1619, 3)
(1620, 3)
(1621, 3)
(1622, 3)
(1623, 3)
(1624, 3)
(1625, 3)
(1626, 3)
(1627, 3)
(1628, 3)
(1629, 3)
(1630, 3)
(1631, 3)
(1632, 3)
(1633, 3)
(1634, 3)
(1635, 3)
(1636, 3)
(1637, 3)
(1638, 3)
(1639, 3)
(1640, 3)
(1641, 3)
(1642, 3)
(1643, 3)
(1644, 3)
(1645, 3)
(1646, 3)
(1647, 3)
(1648, 3)
(1649, 3)
(1650, 3)
(1651, 3)
(1652, 3)
(1653, 3)
(1654, 3)
(1655, 3)
(1656, 3)
(1657, 3)
(1658, 3)
(1659, 3)
(1660, 3)
(1661, 3)
(1662, 3)
(1663, 3)
(1664, 3)
(1665, 3)
(1666, 3)
(1667, 3)
(1668, 3)
(1669, 3)
(1670, 3)
(1671, 3)
(1672, 3)
(1673, 3)
(1674, 3)
(1675, 3)
(1676, 3)
(1677, 3)
(1678, 3)
(1679, 3)
(1680, 3)
(1681, 3)
(1682, 3)
(1683, 3)
(1684, 3)
(1685, 3)
(1686, 3)
(1687, 3)
(1688, 3)
(1689, 3)
(1690, 3)
(1691, 3)
(1692, 3)
(1693, 3)
(1694, 3)
(1695, 3)
(1696, 3)
(1697, 3)
(1698, 3)
(1699, 4)
(1700, 3)
(1701, 3)
(1702, 3)
(1703, 3)
(1704, 3)
(1705, 3)
(1706, 3)
(1707, 3)
(1708, 3)
(1709, 3)
(1710, 3)
(1711, 3)
(1712, 3)
(1713, 3)
(1714, 3)
(1715, 3)
(1716, 3)
(1717, 3)
(1718, 3)
(1719, 3)
(1720, 3)
(1721, 3)
(1722, 3)
(1723, 3)
(1724, 2)
(1725, 2)
(1726, 2)
(1727, 2)
(1728, 2)
(1729, 2)
(1730, 2)
(1731, 2)
(1732, 2)
(1733, 2)
(1734, 2)
(1735, 2)
(1736, 2)
(1737, 2)
(1738, 2)
(1739, 2)
(1740, 2)
(1741, 2)
(1742, 2)
(1743, 2)
(1744, 2)
(1745, 2)
(1746, 2)
(1747, 2)
(1748, 2)
(1749, 2)
(1750, 2)
(1751, 2)
(1752, 2)
(1753, 2)
(1754, 2)
(1755, 2)
(1756, 2)
(1757, 2)
(1758, 2)
(1759, 2)
(1760, 2)
(1761, 2)
(1762, 2)
(1763, 2)
(1764, 2)
(1765, 2)
(1766, 2)
(1767, 2)
(1768, 2)
(1769, 2)
(1770, 2)
(1771, 2)
(1772, 2)
(1773, 2)
(1774, 2)
(1775, 2)
(1776, 2)
(1777, 2)
(1778, 2)
(1779, 2)
(1780, 2)
(1781, 2)
(1782, 2)
(1783, 2)
(1784, 2)
(1785, 2)
(1786, 2)
(1787, 2)
(1788, 2)
(1789, 6)
(1790, 2)
(1791, 2)
(1792, 2)
(1793, 2)
(1794, 2)
(1795, 2)
(1796, 2)
(1797, 2)
(1798, 2)
(1799, 2)
(1800, 2)
(1801, 2)
(1802, 2)
(1803, 2)
(1804, 2)
(1805, 2)
(1806, 2)
(1807, 2)
(1808, 2)
(1809, 2)
(1810, 2)
(1811, 2)
(1812, 2)
(1813, 2)
(1814, 2)
(1815, 2)
(1816, 2)
(1817, 2)
(1818, 2)
(1819, 2)
(1820, 2)
(1821, 2)
(1822, 2)
(1823, 2)
(1824, 2)
(1825, 2)
(1826, 2)
(1827, 2)
(1828, 2)
(1829, 2)
(1830, 2)
(1831, 2)
(1832, 2)
(1833, 2)
(1834, 2)
(1835, 2)
(1836, 2)
(1837, 2)
(1838, 2)
(1839, 2)
(1840, 2)
(1841, 2)
(1842, 2)
(1843, 2)
(1844, 2)
(1845, 2)
(1846, 2)
(1847, 2)
(1848, 2)
(1849, 2)
(1850, 2)
(1851, 2)
(1852, 2)
(1853, 3)
(1854, 2)
(1855, 2)
(1856, 2)
(1857, 2)
(1858, 2)
(1859, 2)
(1860, 2)
(1861, 2)
(1862, 2)
(1863, 2)
(1864, 2)
(1865, 2)
(1866, 2)
(1867, 2)
(1868, 2)
(1869, 2)
(1870, 2)
(1871, 2)
(1872, 2)
(1873, 2)
(1874, 2)
(1875, 2)
(1876, 2)
(1877, 2)
(1878, 2)
(1879, 2)
(1880, 2)
(1881, 2)
(1882, 2)
(1883, 2)
(1884, 2)
(1885, 2)
(1886, 2)
(1887, 2)
(1888, 2)
(1889, 2)
(1890, 2)
(1891, 2)
(1892, 2)
(1893, 2)
(1894, 2)
(1895, 2)
(1896, 2)
(1897, 2)
(1898, 2)
(1899, 2)
(1900, 2)
(1901, 2)
(1902, 2)
(1903, 2)
(1904, 2)
(1905, 2)
(1906, 2)
(1907, 2)
(1908, 2)
(1909, 2)
(1910, 2)
(1911, 2)
(1912, 2)
(1913, 3)
(1914, 2)
(1915, 2)
(1916, 2)
(1917, 2)
(1918, 2)
(1919, 2)
(1920, 2)
(1921, 2)
(1922, 2)
(1923, 2)
(1924, 2)
(1925, 2)
(1926, 2)
(1927, 2)
(1928, 2)
(1929, 2)
(1930, 2)
(1931, 2)
(1932, 2)
(1933, 2)
(1934, 2)
(1935, 2)
(1936, 2)
(1937, 2)
(1938, 2)
(1939, 2)
(1940, 2)
(1941, 2)
(1942, 2)
(1943, 2)
(1944, 2)
(1945, 2)
(1946, 2)
(1947, 2)
(1948, 2)
(1949, 2)
(1950, 2)
(1951, 2)
(1952, 2)
(1953, 2)
(1954, 2)
(1955, 2)
(1956, 2)
(1957, 2)
(1958, 3)
(1959, 2)
(1960, 2)
(1961, 2)
(1962, 2)
(1963, 2)
(1964, 2)
(1965, 2)
(1966, 2)
(1967, 2)
(1968, 2)
(1969, 2)
(1970, 2)
(1971, 2)
(1972, 2)
(1973, 2)
(1974, 2)
(1975, 2)
(1976, 2)
(1977, 2)
(1978, 2)
(1979, 2)
(1980, 2)
(1981, 2)
(1982, 2)
(1983, 2)
(1984, 2)
(1985, 2)
(1986, 2)
(1987, 2)
(1988, 2)
(1989, 2)
(1990, 2)
(1991, 2)
(1992, 2)
(1993, 2)
(1994, 2)
(1995, 2)
(1996, 2)
(1997, 2)
(1998, 2)
(1999, 2)
(2000, 2)
(2001, 2)
(2002, 2)
(2003, 2)
(2004, 2)
(2005, 2)
(2006, 2)
(2007, 2)
(2008, 2)
(2009, 2)
(2010, 2)
(2011, 2)
(2012, 2)
(2013, 2)
(2014, 2)
(2015, 2)
(2016, 2)
(2017, 2)
(2018, 2)
(2019, 2)
(2020, 2)
(2021, 2)
(2022, 2)
(2023, 2)
(2024, 2)
(2025, 2)
(2026, 2)
(2027, 2)
(2028, 2)
(2029, 2)
(2030, 2)
(2031, 2)
(2032, 2)
(2033, 2)
(2034, 2)
(2035, 2)
(2036, 2)
(2037, 2)
(2038, 2)
(2039, 2)
(2040, 2)
(2041, 2)
(2042, 2)
(2043, 2)
(2044, 2)
(2045, 2)
(2046, 2)
(2047, 2)
(2048, 2)
(2049, 2)
(2050, 2)
(2051, 2)
(2052, 2)
(2053, 2)
(2054, 2)
(2055, 2)
(2056, 2)
(2057, 2)
(2058, 2)
(2059, 2)
(2060, 2)
(2061, 2)
(2062, 2)
(2063, 2)
(2064, 2)
(2065, 2)
(2066, 2)
(2067, 2)
(2068, 2)
(2069, 2)
(2070, 2)
(2071, 2)
(2072, 2)
(2073, 2)
(2074, 2)
(2075, 2)
(2076, 2)
(2077, 2)
(2078, 2)
(2079, 2)
(2080, 2)
(2081, 2)
(2082, 2)
(2083, 2)
(2084, 2)
(2085, 2)
(2086, 2)
(2087, 2)
(2088, 2)
(2089, 2)
(2090, 2)
(2091, 2)
(2092, 2)
(2093, 2)
(2094, 2)
(2095, 2)
(2096, 2)
(2097, 2)
(2098, 2)
(2099, 2)
(2100, 2)
(2101, 2)
(2102, 2)
(2103, 2)
(2104, 2)
(2105, 2)
(2106, 2)
(2107, 2)
(2108, 2)
(2109, 2)
(2110, 2)
(2111, 2)
(2112, 2)
(2113, 2)
(2114, 2)
(2115, 2)
(2116, 2)
(2117, 2)
(2118, 2)
(2119, 2)
(2120, 2)
(2121, 2)
(2122, 2)
(2123, 4)
(2124, 2)
(2125, 2)
(2126, 2)
(2127, 2)
(2128, 2)
(2129, 2)
(2130, 2)
(2131, 2)
(2132, 2)
(2133, 2)
(2134, 2)
(2135, 2)
(2136, 2)
(2137, 2)
(2138, 2)
(2139, 2)
(2140, 2)
(2141, 2)
(2142, 2)
(2143, 3)
(2144, 2)
(2145, 2)
(2146, 2)
(2147, 2)
(2148, 2)
(2149, 2)
(2150, 2)
(2151, 2)
(2152, 2)
(2153, 2)
(2154, 2)
(2155, 2)
(2156, 2)
(2157, 2)
(2158, 2)
(2159, 2)
(2160, 2)
(2161, 2)
(2162, 2)
(2163, 2)
(2164, 2)
(2165, 2)
(2166, 2)
(2167, 2)
(2168, 2)
(2169, 2)
(2170, 2)
(2171, 2)
(2172, 2)
(2173, 2)
(2174, 2)
(2175, 2)
(2176, 2)
(2177, 2)
(2178, 2)
(2179, 2)
(2180, 2)
(2181, 2)
(2182, 2)
(2183, 2)
(2184, 2)
(2185, 2)
(2186, 2)
(2187, 2)
(2188, 2)
(2189, 2)
(2190, 2)
(2191, 2)
(2192, 2)
(2193, 2)
(2194, 2)
(2195, 2)
(2196, 2)
(2197, 2)
(2198, 2)
(2199, 2)
(2200, 2)
(2201, 2)
(2202, 2)
(2203, 2)
(2204, 2)
(2205, 2)
(2206, 2)
(2207, 2)
(2208, 2)
(2209, 2)
(2210, 2)
(2211, 2)
(2212, 2)
(2213, 2)
(2214, 2)
(2215, 2)
(2216, 2)
(2217, 1)
(2218, 1)
(2219, 1)
(2220, 1)
(2221, 1)
(2222, 1)
(2223, 1)
(2224, 1)
(2225, 1)
(2226, 1)
(2227, 1)
(2228, 1)
(2229, 1)
(2230, 1)
(2231, 1)
(2232, 3)
(2233, 1)
(2234, 1)
(2235, 1)
(2236, 1)
(2237, 1)
(2238, 1)
(2239, 1)
(2240, 1)
(2241, 1)
(2242, 1)
(2243, 1)
(2244, 1)
(2245, 1)
(2246, 1)
(2247, 1)
(2248, 1)
(2249, 2)
(2250, 1)
(2251, 1)
(2252, 1)
(2253, 1)
(2254, 1)
(2255, 1)
(2256, 1)
(2257, 1)
(2258, 1)
(2259, 1)
(2260, 1)
(2261, 1)
(2262, 2)
(2263, 1)
(2264, 1)
(2265, 1)
(2266, 1)
(2267, 1)
(2268, 1)
(2269, 1)
(2270, 1)
(2271, 1)
(2272, 1)
(2273, 1)
(2274, 1)
(2275, 1)
(2276, 1)
(2277, 1)
(2278, 1)
(2279, 1)
(2280, 1)
(2281, 1)
(2282, 1)
(2283, 1)
(2284, 1)
(2285, 1)
(2286, 1)
(2287, 1)
(2288, 1)
(2289, 1)
(2290, 1)
(2291, 1)
(2292, 1)
(2293, 1)
(2294, 1)
(2295, 1)
(2296, 1)
(2297, 1)
(2298, 1)
(2299, 1)
(2300, 1)
(2301, 1)
(2302, 1)
(2303, 1)
(2304, 1)
(2305, 1)
(2306, 1)
(2307, 9)
(2308, 1)
(2309, 1)
(2310, 1)
(2311, 1)
(2312, 1)
(2313, 1)
(2314, 1)
(2315, 1)
(2316, 1)
(2317, 1)
(2318, 1)
(2319, 1)
(2320, 1)
(2321, 1)
(2322, 1)
(2323, 1)
(2324, 1)
(2325, 1)
(2326, 1)
(2327, 1)
(2328, 1)
(2329, 1)
(2330, 1)
(2331, 1)
(2332, 1)
(2333, 1)
(2334, 1)
(2335, 1)
(2336, 1)
(2337, 1)
(2338, 1)
(2339, 1)
(2340, 1)
(2341, 1)
(2342, 2)
(2343, 1)
(2344, 1)
(2345, 1)
(2346, 1)
(2347, 1)
(2348, 4)
(2349, 1)
(2350, 1)
(2351, 1)
(2352, 1)
(2353, 1)
(2354, 1)
(2355, 1)
(2356, 1)
(2357, 1)
(2358, 1)
(2359, 1)
(2360, 1)
(2361, 1)
(2362, 1)
(2363, 1)
(2364, 1)
(2365, 1)
(2366, 1)
(2367, 1)
(2368, 1)
(2369, 1)
(2370, 1)
(2371, 1)
(2372, 1)
(2373, 1)
(2374, 1)
(2375, 1)
(2376, 1)
(2377, 1)
(2378, 1)
(2379, 1)
(2380, 1)
(2381, 1)
(2382, 1)
(2383, 1)
(2384, 1)
(2385, 1)
(2386, 1)
(2387, 1)
(2388, 1)
(2389, 1)
(2390, 1)
(2391, 1)
(2392, 1)
(2393, 1)
(2394, 1)
(2395, 1)
(2396, 1)
(2397, 1)
(2398, 1)
(2399, 1)
(2400, 1)
(2401, 1)
(2402, 1)
(2403, 1)
(2404, 1)
(2405, 1)
(2406, 1)
(2407, 1)
(2408, 1)
(2409, 1)
(2410, 1)
(2411, 1)
(2412, 1)
(2413, 1)
(2414, 1)
(2415, 1)
(2416, 1)
(2417, 1)
(2418, 1)
(2419, 1)
(2420, 1)
(2421, 1)
(2422, 1)
(2423, 1)
(2424, 1)
(2425, 1)
(2426, 1)
(2427, 1)
(2428, 1)
(2429, 1)
(2430, 1)
(2431, 1)
(2432, 1)
(2433, 1)
(2434, 1)
(2435, 1)
(2436, 1)
(2437, 1)
(2438, 1)
(2439, 1)
(2440, 1)
(2441, 1)
(2442, 1)
(2443, 1)
(2444, 1)
(2445, 1)
(2446, 1)
(2447, 1)
(2448, 1)
(2449, 1)
(2450, 1)
(2451, 1)
(2452, 1)
(2453, 1)
(2454, 1)
(2455, 1)
(2456, 1)
(2457, 1)
(2458, 1)
(2459, 1)
(2460, 1)
(2461, 1)
(2462, 1)
(2463, 1)
(2464, 1)
(2465, 1)
(2466, 1)
(2467, 1)
(2468, 1)
(2469, 1)
(2470, 1)
(2471, 1)
(2472, 1)
(2473, 1)
(2474, 1)
(2475, 1)
(2476, 1)
(2477, 1)
(2478, 1)
(2479, 1)
(2480, 1)
(2481, 1)
(2482, 1)
(2483, 1)
(2484, 1)
(2485, 1)
(2486, 1)
(2487, 1)
(2488, 4)
(2489, 1)
(2490, 1)
(2491, 1)
(2492, 1)
(2493, 1)
(2494, 1)
(2495, 1)
(2496, 1)
(2497, 1)
(2498, 1)
(2499, 1)
(2500, 1)
(2501, 1)
(2502, 1)
(2503, 1)
(2504, 1)
(2505, 1)
(2506, 1)
(2507, 1)
(2508, 1)
(2509, 1)
(2510, 1)
(2511, 1)
(2512, 1)
(2513, 1)
(2514, 1)
(2515, 1)
(2516, 1)
(2517, 1)
(2518, 1)
(2519, 1)
(2520, 1)
(2521, 1)
(2522, 1)
(2523, 1)
(2524, 1)
(2525, 1)
(2526, 1)
(2527, 1)
(2528, 1)
(2529, 1)
(2530, 1)
(2531, 1)
(2532, 1)
(2533, 1)
(2534, 1)
(2535, 1)
(2536, 1)
(2537, 1)
(2538, 1)
(2539, 1)
(2540, 1)
(2541, 1)
(2542, 1)
(2543, 1)
(2544, 1)
(2545, 1)
(2546, 1)
(2547, 1)
(2548, 1)
(2549, 1)
(2550, 1)
(2551, 1)
(2552, 1)
(2553, 1)
(2554, 1)
(2555, 1)
(2556, 1)
(2557, 1)
(2558, 1)
(2559, 1)
(2560, 1)
(2561, 1)
(2562, 1)
(2563, 1)
(2564, 1)
(2565, 1)
(2566, 1)
(2567, 1)
(2568, 1)
(2569, 1)
(2570, 1)
(2571, 1)
(2572, 1)
(2573, 1)
(2574, 1)
(2575, 1)
(2576, 1)
(2577, 1)
(2578, 1)
(2579, 1)
(2580, 1)
(2581, 1)
(2582, 1)
(2583, 1)
(2584, 1)
(2585, 1)
(2586, 1)
(2587, 1)
(2588, 1)
(2589, 1)
(2590, 1)
(2591, 1)
(2592, 1)
(2593, 1)
(2594, 1)
(2595, 1)
(2596, 1)
(2597, 1)
(2598, 1)
(2599, 1)
(2600, 1)
(2601, 1)
(2602, 1)
(2603, 1)
(2604, 1)
(2605, 1)
(2606, 1)
(2607, 1)
(2608, 1)
(2609, 1)
(2610, 1)
(2611, 1)
(2612, 1)
(2613, 1)
(2614, 1)
(2615, 1)
(2616, 1)
(2617, 1)
(2618, 1)
(2619, 1)
(2620, 1)
(2621, 1)
(2622, 1)
(2623, 1)
(2624, 1)
(2625, 1)
(2626, 1)
(2627, 1)
(2628, 1)
(2629, 1)
(2630, 1)
(2631, 1)
(2632, 1)
(2633, 1)
(2634, 1)
(2635, 1)
(2636, 1)
(2637, 1)
(2638, 1)
(2639, 1)
(2640, 1)
(2641, 1)
(2642, 1)
(2643, 1)
(2644, 1)
(2645, 1)
(2646, 1)
(2647, 1)
(2648, 1)
(2649, 1)
(2650, 1)
(2651, 1)
(2652, 1)
(2653, 1)
(2654, 1)
(2655, 1)
(2656, 1)
(2657, 1)
(2658, 1)
(2659, 1)
(2660, 1)
(2661, 1)
(2662, 1)
(2663, 1)
(2664, 1)
(2665, 1)
(2666, 1)
(2667, 1)
(2668, 1)
(2669, 1)
(2670, 1)
(2671, 1)
(2672, 1)
(2673, 1)
(2674, 1)
(2675, 1)
(2676, 1)
(2677, 1)
(2678, 1)
(2679, 1)
(2680, 1)
(2681, 1)
(2682, 1)
(2683, 1)
(2684, 1)
(2685, 1)
(2686, 1)
(2687, 1)
(2688, 1)
(2689, 1)
(2690, 1)
(2691, 1)
(2692, 1)
(2693, 1)
(2694, 1)
(2695, 1)
(2696, 1)
(2697, 1)
(2698, 1)
(2699, 1)
(2700, 1)
(2701, 1)
(2702, 1)
(2703, 1)
(2704, 1)
(2705, 1)
(2706, 1)
(2707, 1)
(2708, 1)
(2709, 1)
(2710, 1)
(2711, 1)
(2712, 1)
(2713, 1)
(2714, 1)
(2715, 1)
(2716, 1)
(2717, 1)
(2718, 1)
(2719, 1)
(2720, 1)
(2721, 1)
(2722, 1)
(2723, 1)
(2724, 1)
(2725, 1)
(2726, 1)
(2727, 1)
(2728, 1)
(2729, 1)
(2730, 1)
(2731, 1)
(2732, 1)
(2733, 1)
(2734, 1)
(2735, 1)
(2736, 1)
(2737, 1)
(2738, 1)
(2739, 1)
(2740, 1)
(2741, 1)
(2742, 1)
(2743, 1)
(2744, 1)
(2745, 1)
(2746, 1)
(2747, 1)
(2748, 1)
(2749, 1)
(2750, 1)
(2751, 1)
(2752, 1)
(2753, 1)
(2754, 1)
(2755, 1)
(2756, 1)
(2757, 1)
(2758, 1)
(2759, 1)
(2760, 1)
(2761, 1)
(2762, 1)
(2763, 1)
(2764, 1)
(2765, 1)
(2766, 1)
(2767, 1)
(2768, 1)
(2769, 1)
(2770, 1)
(2771, 1)
(2772, 1)
(2773, 1)
(2774, 1)
(2775, 1)
(2776, 1)
(2777, 1)
(2778, 1)
(2779, 1)
(2780, 1)
(2781, 1)
(2782, 1)
(2783, 1)
(2784, 1)
(2785, 1)
(2786, 1)
(2787, 1)
(2788, 1)
(2789, 1)
(2790, 1)
(2791, 1)
(2792, 1)
(2793, 1)
(2794, 1)
(2795, 1)
(2796, 1)
(2797, 1)
(2798, 1)
(2799, 1)
(2800, 1)
(2801, 1)
(2802, 1)
(2803, 1)
(2804, 1)
(2805, 1)
(2806, 1)
(2807, 1)
(2808, 1)
(2809, 1)
(2810, 1)
(2811, 1)
(2812, 1)
(2813, 1)
(2814, 1)
(2815, 1)
(2816, 1)
(2817, 1)
(2818, 1)
(2819, 1)
(2820, 1)
(2821, 1)
(2822, 1)
(2823, 1)
(2824, 1)
(2825, 1)
(2826, 1)
(2827, 1)
(2828, 1)
(2829, 1)
(2830, 1)
(2831, 1)
(2832, 1)
(2833, 1)
(2834, 1)
(2835, 1)
(2836, 1)
(2837, 1)
(2838, 1)
(2839, 1)
(2840, 1)
(2841, 1)
(2842, 1)
(2843, 1)
(2844, 1)
(2845, 1)
(2846, 1)
(2847, 1)
(2848, 1)
(2849, 1)
(2850, 1)
(2851, 1)
(2852, 1)
(2853, 1)
(2854, 1)
(2855, 1)
(2856, 1)
(2857, 1)
(2858, 1)
(2859, 1)
(2860, 1)
(2861, 1)
(2862, 1)
(2863, 1)
(2864, 1)
(2865, 1)
(2866, 1)
(2867, 1)
(2868, 7)
(2869, 1)
(2870, 1)
(2871, 1)
(2872, 1)
(2873, 1)
(2874, 1)
(2875, 1)
(2876, 1)
(2877, 1)
(2878, 1)
(2879, 1)
(2880, 1)
(2881, 1)
(2882, 1)
(2883, 1)
(2884, 1)
(2885, 1)
(2886, 1)
(2887, 1)
(2888, 1)
(2889, 1)
(2890, 1)
(2891, 1)
(2892, 1)
(2893, 1)
(2894, 1)
(2895, 1)
(2896, 1)
(2897, 1)
(2898, 1)
(2899, 1)
(2900, 1)
(2901, 1)
(2902, 1)
(2903, 1)
(2904, 1)
(2905, 1)
(2906, 1)
(2907, 1)
(2908, 1)
(2909, 1)
(2910, 1)
(2911, 1)
(2912, 1)
(2913, 1)
(2914, 1)
(2915, 1)
(2916, 1)
(2917, 1)
(2918, 1)
(2919, 1)
(2920, 1)
(2921, 1)
(2922, 1)
(2923, 1)
(2924, 1)
(2925, 1)
(2926, 1)
(2927, 1)
(2928, 1)
(2929, 1)
(2930, 1)
(2931, 1)
(2932, 1)
(2933, 1)
(2934, 1)
(2935, 1)
(2936, 1)
(2937, 1)
(2938, 1)
(2939, 1)
(2940, 1)
(2941, 1)
(2942, 1)
(2943, 1)
(2944, 1)
(2945, 1)
(2946, 1)
(2947, 1)
(2948, 1)
(2949, 1)
(2950, 1)
(2951, 1)
(2952, 1)
(2953, 1)
(2954, 1)
(2955, 1)
(2956, 1)
(2957, 1)
(2958, 1)
(2959, 1)
(2960, 1)
(2961, 1)
(2962, 1)
(2963, 1)
(2964, 1)
(2965, 1)
(2966, 1)
(2967, 1)
(2968, 1)
(2969, 1)
(2970, 1)
(2971, 1)
(2972, 1)
(2973, 1)
(2974, 1)
(2975, 1)
(2976, 1)
(2977, 1)
(2978, 1)
(2979, 1)
(2980, 1)
(2981, 1)
(2982, 1)
(2983, 1)
(2984, 1)
(2985, 1)
(2986, 1)
(2987, 1)
(2988, 1)
(2989, 1)
(2990, 1)
(2991, 1)
(2992, 1)
(2993, 1)
(2994, 1)
(2995, 1)
(2996, 1)
(2997, 1)
(2998, 1)
(2999, 1)
(3000, 1)
(3001, 1)
(3002, 1)
(3003, 1)
(3004, 1)
(3005, 1)
(3006, 1)
(3007, 1)
(3008, 1)
(3009, 1)
(3010, 1)
(3011, 1)
(3012, 1)
(3013, 2)
(3014, 1)
(3015, 1)
(3016, 1)
(3017, 1)
(3018, 1)
(3019, 1)
(3020, 1)
(3021, 1)
(3022, 1)
(3023, 1)
(3024, 1)
(3025, 1)
(3026, 1)
(3027, 1)
(3028, 1)
(3029, 1)
(3030, 1)
(3031, 1)
(3032, 1)
(3033, 1)
(3034, 1)
(3035, 1)
(3036, 1)
(3037, 1)
(3038, 1)
(3039, 1)
(3040, 1)
(3041, 1)
(3042, 1)
(3043, 1)
(3044, 1)
(3045, 1)
(3046, 1)
(3047, 1)
(3048, 1)
(3049, 1)
(3050, 1)
(3051, 1)
(3052, 1)
(3053, 1)
(3054, 1)
(3055, 1)
(3056, 1)
(3057, 9)
(3058, 1)
(3059, 1)
(3060, 1)
(3061, 1)
(3062, 1)
(3063, 1)
(3064, 1)
(3065, 1)
(3066, 1)
(3067, 1)
(3068, 1)
(3069, 1)
(3070, 1)
(3071, 1)
(3072, 1)
(3073, 1)
(3074, 1)
(3075, 1)
(3076, 1)
(3077, 1)
(3078, 1)
(3079, 1)
(3080, 1)
(3081, 1)
(3082, 1)
(3083, 1)
(3084, 1)
(3085, 1)
(3086, 1)
(3087, 1)
(3088, 1)
(3089, 1)
(3090, 1)
(3091, 1)
(3092, 1)
(3093, 1)
(3094, 1)
(3095, 1)
(3096, 1)
(3097, 1)
(3098, 1)
(3099, 1)
(3100, 1)
(3101, 1)
(3102, 1)
(3103, 1)
(3104, 1)
(3105, 1)
(3106, 1)
(3107, 1)
(3108, 1)
(3109, 1)
(3110, 1)
(3111, 1)
(3112, 1)
(3113, 1)
(3114, 1)
(3115, 1)
(3116, 1)
(3117, 1)
(3118, 1)
(3119, 1)
(3120, 1)
(3121, 1)
(3122, 1)
(3123, 1)
(3124, 1)
(3125, 1)
(3126, 1)
(3127, 1)
(3128, 1)
(3129, 1)
(3130, 1)
(3131, 1)
(3132, 1)
(3133, 1)
(3134, 1)
(3135, 1)
(3136, 1)
(3137, 1)
(3138, 1)
(3139, 1)
(3140, 1)
(3141, 1)
(3142, 1)
(3143, 1)
(3144, 1)
(3145, 1)
(3146, 1)
(3147, 1)
(3148, 1)
(3149, 1)
(3150, 1)
(3151, 1)
(3152, 1)
(3153, 1)
(3154, 1)
(3155, 1)
(3156, 1)
(3157, 1)
(3158, 1)
(3159, 1)
(3160, 1)
(3161, 1)
(3162, 1)
(3163, 1)
(3164, 1)
(3165, 1)
(3166, 1)
(3167, 1)
(3168, 1)
(3169, 1)
(3170, 1)
(3171, 1)
(3172, 1)
(3173, 1)
(3174, 1)
(3175, 1)
(3176, 1)
(3177, 1)
(3178, 1)
(3179, 1)
(3180, 1)
(3181, 1)
(3182, 1)
(3183, 1)
(3184, 1)
(3185, 1)
(3186, 1)
(3187, 1)
(3188, 1)
(3189, 1)
(3190, 1)
(3191, 1)
(3192, 1)
(3193, 1)
(3194, 1)
(3195, 1)
(3196, 1)
(3197, 1)
(3198, 1)
(3199, 1)
(3200, 5)
(3201, 1)
(3202, 1)
(3203, 1)
(3204, 1)
(3205, 1)
(3206, 1)
(3207, 1)
(3208, 1)
(3209, 1)
(3210, 1)
(3211, 1)
(3212, 1)
(3213, 1)
(3214, 1)
(3215, 1)
(3216, 1)
(3217, 1)
(3218, 1)
(3219, 1)
(3220, 1)
(3221, 1)
(3222, 1)
(3223, 1)
(3224, 1)
(3225, 1)
(3226, 1)
(3227, 1)
(3228, 1)
(3229, 1)



In [7]:

    
#Determining the labels with counts more than 15
labels_unique_more = []
for index, cnt in enumerate(labels_counts):
    if cnt > 15:
        labels_unique_more.append(labels_unique[index])

print('Number of labels with counts more than 15: %d' % len(labels_unique_more))









    



Number of labels with counts more than 15: 593



In [8]:

    
#Determining cluster centers for the labels with counts more than 15
cluster_centers_more = np.empty( (len(labels_unique_more), 2) )
for index, lbl in enumerate(labels_unique_more):
    cluster_centers_more[index] = cluster_centers[lbl]

print(cluster_centers_more)









    



[[  40.7177164   -73.99183542]
 [  33.44943805 -112.00213969]
 [  33.44638027 -111.90188756]
 ..., 
 [  41.61853175  -88.44556818]
 [  38.65877915  -76.8856871 ]
 [  39.2494686   -77.1821271 ]]

Как мы помним, 20 баннеров надо разместить близ офисов компании. Найдем на Google Maps по запросу Carnival Cruise Line адреса всех офисов:

33.751277, -118.188740 (Los Angeles)

25.867736, -80.324116 (Miami)

51.503016, -0.075479 (London)

52.378894, 4.885084 (Amsterdam)

39.366487, 117.036146 (Beijing)

-33.868457, 151.205134 (Sydney)

Осталось определить 20 ближайших к ним центров кластеров. Т.е. посчитать дистанцию до ближайшего офиса для каждой точки и выбрать 20 с наименьшим значением.



In [9]:

    
#Reading the Carnival Cruise Line offices file
offices = pd.read_csv('carnival_cruise_lines_officies.txt', skipinitialspace=True)
print(offices.info())
offices_for_dist = offices.loc[:, ['latitude', 'longitude']]
offices_for_dist









    



<class 'pandas.core.frame.DataFrame'>
RangeIndex: 6 entries, 0 to 5
Data columns (total 3 columns):
latitude     6 non-null float64
longitude    6 non-null float64
city         6 non-null object
dtypes: float64(2), object(1)
memory usage: 216.0+ bytes
None






    Out[9]:







  
    
      
      latitude
      longitude
    
  
  
    
      0
      33.751277
      -118.188740
    
    
      1
      25.867736
      -80.324116
    
    
      2
      51.503016
      -0.075479
    
    
      3
      52.378894
      4.885084
    
    
      4
      39.366487
      117.036146
    
    
      5
      -33.868457
      151.205134



In [10]:

    
def distance(x, y):
    return np.sqrt( np.sum((x - y)**2) )



In [11]:

    
#Calculating distances from nearest offices
distances_from_nearest_office = np.empty( cluster_centers_more.shape[0] )
for i, item in enumerate(cluster_centers_more):
    min_dist = distance(item, offices_for_dist.loc[0])
    for j in range(len(offices)):
        dist = distance(item, offices_for_dist.loc[j])
        if dist < min_dist:
            min_dist = dist
    distances_from_nearest_office[i] = min_dist



In [12]:

    
#Sorting arrays on minimum distance
dist_sorted_indices = np.argsort(distances_from_nearest_office)
distances_from_nearest_office_sorted = distances_from_nearest_office[dist_sorted_indices]
cluster_centers_more_sorted = cluster_centers_more[dist_sorted_indices]

Для сдачи задания выберите из получившихся 20 центров тот, который наименее удален от ближайшего к нему офиса. Ответ в этом задании — широта и долгота этого центра, записанные через пробел.



In [13]:

    
print('Minimal distance: %f' % distances_from_nearest_office_sorted[0])
print('Coordinates of closest centroid: %s' % str(cluster_centers_more_sorted[0]))









    



Minimal distance: 0.007835
Coordinates of closest centroid: [ -33.86063043  151.20477593]



In [14]:

    
#Writing the answer to the file
answer = str(cluster_centers_more_sorted[0, 0]) + ' ' + str(cluster_centers_more_sorted[0, 1])
with open('answer.txt', 'w') as fout:
    fout.write(answer)

	id	user_id	venue_id	latitude	longitude	created_at
0	984301	2041916.0	5222.0	NaN	NaN	2012-04-21 17:39:01
1	984222	15824.0	5222.0	38.895112	-77.036366	2012-04-21 17:43:47
2	984315	1764391.0	5222.0	NaN	NaN	2012-04-21 17:37:18
3	984234	44652.0	5222.0	33.800745	-84.410520	2012-04-21 17:43:43
4	984249	2146840.0	5222.0	NaN	NaN	2012-04-21 17:42:58

	latitude	longitude
0	33.751277	-118.188740
1	25.867736	-80.324116
2	51.503016	-0.075479
3	52.378894	4.885084
4	39.366487	117.036146
5	-33.868457	151.205134